package LeetCode.t22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Laity
 * @Project: JavaLaity
 * @Package: LeetCode.t22.GenerateParenthesis
 * @Date: 2022年11月13日 19:03
 * @Description: Leetcode第22题：括号生成
 * 回溯算法: 先写n个左括号，然后就写右括号，每当完成一组之后，就吧字符串存起来。然后再倒退步骤到写第n-1个左括号，然后写右括号，在写左括号，再全写右括号。依次回溯递归，每完成一趟就回到能再改变的位置。
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 时间复杂度：O(logn)
 */
public class GenerateParenthesis {

    public static List<String> generateParenthesis(int n) {
        List<String> arr = new ArrayList<String>();//定义集合用来接收最后的的字符串集合
        String temp = ""; //用来接收递归时每一层的字符串
        genBack(n, n, temp, arr); //递归
        return arr;
    }

    /**
     * 逻辑
     * @param left 剩下的(个数
     * @param right 剩下的)个数
     * @param temp 用来接收递归时每一层的字符串
     * @param arr 定义集合用来接收最后的的字符串集合
     */
    static void genBack(int left, int right, String temp, List<String> arr) {
        //递归，left为剩下的(个数，right为剩下的)个数，
        if (left < 0 || right < 0 || left > right) {
            //如果left>right，则表示递归的时候right进入多了，字符串将会是(()))的错误形式
            return;
        }
        if (left == 0 && right == 0) {
            //即将所有括号全部添加完
            arr.add(temp); //加入集合
            return;
        }
        genBack(left - 1, right, temp + "(", arr); //先递归 "("
        genBack(left, right - 1, temp + ")", arr); //递归 ")"
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println(generateParenthesis(3).toString());
    }


    public List<String> generateParenthesis1(int n) {
        List<String> list = new ArrayList<>();
        chuli("", list, n, n);
        return list;
    }

    public static void chuli(String s, List<String> list, int left, int right) {
        if (left > right) {
            return;
        }

        if (left > 0) {
            chuli(s + "(", list, left - 1, right);
        }
        if (right > 0) {
            chuli(s + ")", list, left, right - 1);
        }
        if (left == 0 && right == 0) {
            list.add(s);
            return;
        }
    }
}
